#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

constexpr int N = 100010;
constexpr int M = 100010;
/*
 * 学习方法：
 * 1、上课讲模板
 * 2、理解并记忆模版，能写出来并且调试通过
 * 3、练习题目，应用模板，擦了重写，3~5次
 * /

/*
 * 快速排序 --- 分治
 * 1、确定分界点x: q[l],q[r],q[(l+r)/2],随机
 * 2、调整区间：左边都<=x，右边都>=x，注意等于x情况可以在两边
 * 3、递归处理，左右两段
 *
 */

void QuickSort(int q[], const int left, const int right)
{
    if (left >= right)
        return;

    const int x = q[left];
    int i = left - 1, j = right + 1;
    while (i < j) {
        do ++i; while (q[i] < x);
        do --j; while (q[j] > x);
        if (i < j) {
            swap(q[i], q[j]);
        }
    }
    QuickSort(q, left, j);
    QuickSort(q, j + 1, right);
}

void Run()
{
    int n;
    int arr[N];

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    sort(arr, arr + n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

/*
 * 归并排序 --- 分治
 * 1、确定分界点: mid = (l+r)/2
 * 2、递归排序left，right
 * 3、归并 --- 合二为一
 *
 */

void MergeSort(int arr[], const int left, const int right)
{
    if (left >= right) return;
    const int mid = left + right >> 1;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    int i = left, j = mid + 1, k = 0;
    int tmp[N];
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    for (int i = left, j = 0; i <= right; i++, j++) arr[i] = tmp[j];
}

/*
 * 前缀和 就是数列前n项和
 * 作用，能快速求出来某区间的所有的和
 *
 */

void Sum(const int max, const int a[N], int sum[N])
{
    sum[0] = 0;
    for (int i = 1; i <= max; ++i) {
        sum[i] = sum[i - 1] + a[i];
    }

    // [l, r]区间
    int l, r;
    int j = sum[r] - sum[l - 1];
}

/*
 * 二维前缀和 就是求子矩阵的
 *
 *
 *
 */

void MatrixSum()
{
    int n,m;
    int maxSize = 0;
    scanf_s("%d%d%d", &n, &m);

    // 使用 n + 1,从1开始省边界条件判断
    vector<vector<int>> matrixA(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> matrixSum(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            scanf_s("%d", &matrixA[i][j]);
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 前缀和
            matrixSum[i][j] = matrixSum[i - 1][j] + matrixSum[i][j - 1]
                - matrixSum[i - 1][j - 1] + matrixA[i][j];
            for(int k = 1; k < i; ++k) {
                for(int l = 1; l < j; ++l) {
                    // 子矩阵和
                    int sum = matrixSum[i][j] - matrixSum[k - 1][j] - matrixSum[i][l - 1]
                        + matrixSum[k - 1][l - 1];
                    if (sum == 1) {
                        // 子矩阵面积
                        int mianji = (i - k + 1) * (j - l + 1);
                        maxSize = max(mianji, maxSize);
                    }
                }
            }
        }
    }

    printf("%d\n", maxSize);
}

/*
 * 差分就是，把每个数插进去就行
 *
 *
 */

void insert(int x1, int y1, int x2, int y2, int c, int b[N][N])
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

void difference()
{
    int n,m,q;
    int a[N][N];
    int b[N][N];
    for(int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            insert(i, j, i, j, a[i][j], b);
        }
    }
}

/*
 * 双指针算法
 *
 *
 */

void func()
{
    int n = 0;
    auto check = [](int i, int j) -> bool {

        return j < i;
    };

    for (int i = 0, j = 0; i < n; ++i) {
        while(j < i && check(i, j)) ++j;
    }
}

/*
 * 常用的位运算操作
 * 1\先把第k位移到最后一位，n >> k
 * 2\看一下各位是几， x&1
 * n >> k & 1
 *
 * lowbit(x): 返回x的最后一位1 x = 1010 -> 10
 * x=101000 -> 1000
 * lowbit(x) = x&(~x + 1)
 */

1:10:00





